home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 412_01 / demos / demo5.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-28  |  4.5 KB  |  174 lines

  1. #include "demo5.h"
  2.  
  3. /*
  4.  
  5.     Database of (routes between) cities and associated distances.
  6.  
  7. */
  8.  
  9. ROUTE_
  10.     table[] = {
  11.                 { "amsterdam", "hamburg" ,440 },
  12.                 { "amsterdam", "londen", 550 },
  13.                 { "amsterdam", "brussel", 210 },
  14.                 { "amsterdam", "keulen", 250 },
  15.                 { "brussel", "frankfort", 410},
  16.                 { "brussel", "parijs", 560 },
  17.                 { "brussel", "londen", 390 },
  18.                 { "brussel", "luxemburg", 220},
  19.                 { "brussel", "keulen" , 220 },
  20.                 { "bordeaux", "madrid" ,690 },
  21.                 { "bordeaux", "marseille", 630 },
  22.                 { "keulen", "hamburg", 430 },
  23.                 { "keulen", "frankfort", 200},
  24.                 { "keulen", "luxemburg", 200},
  25.                 { "keulen", "basel", 480},
  26.                 { "parijs", "bordeaux", 560},
  27.                 { "parijs", "marseille", 770},
  28.                 { "parijs", "luxemburg", 340},
  29.                 { "parijs", "basel", 490},
  30.                 { "madrid", "lissabon", 650},
  31.                 { "marseille", "genua", 400},
  32.                 { "marseille", "bern", 580},
  33.                 { "frankfort", "basel", 330},
  34.                 { "frankfort", "hamburg", 490},
  35.                 { "frankfort", "berlijn", 530},
  36.                 { "frankfort", "wenen", 720},
  37.                 { "bern", "basel", 90},
  38.                 { "bern", "milaan", 350},
  39.                 { "bern", "genua", 490},
  40.                 { "boedapest", "wenen", 250},
  41.                 { "triest", "wenen", 500},
  42.                 { "triest", "milaan", 420},
  43.                 { "triest", "frankfort", 900},
  44.                 { "milaan", "rome", 590},
  45.                 { "hamburg", "kopenhagen", 320},
  46.                 { "genua", "rome", 540},
  47.                 { "genua", "milaan", 140},
  48.                 { "palermo", "rome", 590},
  49.                 { "wenen", "basel", 840},
  50.                 { "wenen", "berlijn", 660},
  51.                 { "wenen", "warschau", 690},
  52.                 { "berlijn", "hamburg", 290},
  53.                 { "berlijn", "amsterdam", 660},
  54.                 { "berlijn", "warschau", 560},
  55.                 { "luxemburg", "frankfort", 230},
  56.                 { "luxemburg", "basel", 330},
  57.                 { NULL, NULL, 0}       // marks end of table
  58.             };
  59.  
  60.  
  61.  
  62.  
  63. PATH_::PATH_(CITY_ *start, CITY_ *target)
  64.     :UNICOST_GRAPH_(start, target, 0)
  65. {
  66. }
  67.  
  68.  
  69.  
  70. CITY_::CITY_(const char *p, int d)
  71. {
  72.     city = p;
  73.     dist = d;
  74. }
  75.  
  76.  
  77.  
  78. /*                  DISPLAY
  79.  
  80.     Displays current city and distance of the path so far.
  81.  
  82. */
  83.  
  84.  
  85. void CITY_::display() const
  86. {
  87.     printf("%15s   %5d\n", city, get_g());
  88. }
  89.  
  90.  
  91.  
  92. int CITY_::equal(const VOBJECT_ &other) const
  93. {
  94.     return(!strcmp(city, ((const CITY_ &)other).getcity()));
  95. }
  96.  
  97.  
  98.  
  99. const char *CITY_::getcity() const
  100. {
  101.     return(city);
  102. }
  103.  
  104.  
  105.  
  106. int CITY_::getdist() const
  107. {
  108.     return(dist);
  109. }
  110.  
  111.  
  112.  
  113. /*                     EXPAND
  114.  
  115.     This function expands the current node by generating all of
  116.     its successor nodes. In this case this means we build a linked
  117.     list of all the cities that are directly reachable from the
  118.     current city. We just scan the database of cities for a match,
  119.     since a city may be in either half of an entry (from A to B ==
  120.     from B to A) we need to check both halves.
  121.  
  122. */
  123.  
  124. NODE_ *CITY_::expand(int ) const
  125. {
  126.     int
  127.         i;
  128.     CITY_
  129.         *start = NULL,
  130.         *tmp;
  131.  
  132.     for (i = 0; table[i].from != NULL; i++)
  133.     {
  134.         if (!strcmp(table[i].from, city)) // found city in first halt of entry
  135.             tmp = new CITY_(table[i].to, table[i].distance);
  136.         else if (!strcmp(table[i].to, city)) // found city in 2nd half of entry
  137.             tmp = new CITY_(table[i].from, table[i].distance);
  138.         else 
  139.             continue;   // no match
  140.  
  141. // found a match
  142.         tmp->setnext(start);    // builds a linked list
  143.     start = tmp;
  144.     }
  145.     return(start);
  146. }
  147.  
  148.  
  149.  
  150. /*                  COMPUT_G
  151.  
  152.     Function compute_g() serves to compute the cost of getting from
  153.     the parent node to the current node. In this case the cost is 
  154.     represented by the distance of the path from the 'parent' city the
  155.     current city, so we just return the distance associated with the city.
  156.  
  157. */
  158.  
  159. int PATH_::compute_g(const NODE_ &node)
  160. {
  161.     return(((const CITY_ &)node).getdist());
  162. }
  163.  
  164.  
  165.  
  166. int main()
  167. {
  168.     PATH_
  169.         path(new CITY_("kopenhagen", 0), new CITY_("rome", 0));
  170.  
  171.     path.generate();
  172.     return(1);
  173. }
  174.